package primary.code03_Heap;

import java.util.Arrays;

/**
 * 计数排序
 * 利用数据样本的特点进行排序，复杂度 O(N)
 * 例如对年龄进行排序，年龄范围为 0 ~ 200
 */
public class Code03_CountSort {

    public static void main(String[] args) {
        int[] arr = {4, 1, 1, 57, 23, 8, 23, 57, 87, 200, 89};
        countSort(arr, 200);
        System.out.println(Arrays.toString(arr));
    }

    private static void countSort(int[] arr, int max) {
        int[] helper = new int[max+1];
        for (int i = 0; i < arr.length; i++) {
            helper[arr[i]] = helper[arr[i]] + 1;
        }
        int index = 0;
        for (int i = 0; i < helper.length; i++) {
            for (int j = 0; j < helper[i]; j++) {
                   arr[index ++] = i;
            }
        }
    }
}
